package wdstruct

type AvlTree struct {
	root *AvlNode
	Compare func(a,b interface{})int //1:a>b  -1:a<b   0:a=b
}

func (a * AvlTree)Insert(data interface{}){
	if a.root == nil{
		a.root = new(AvlNode)
		a.root.Data = data
		a.root.Height = 1
	}
	//a.root = a.root.insert()
}

func (a * AvlTree)Find(data interface{})*AvlNode{
	node := a.root
	for true {
		if node == nil {
			return nil
		}
		switch a.Compare(node.Data,data){
		case 0:
			return node
		case 1:
			if node.Left != nil {
				node = node.Left
			}
		case -1:
			if node.Right != nil{
				node = node.Right
			}
		}
	}
	return nil
}
func (a * AvlTree)FindMax()(*AvlNode,interface{}){
	node := a.root
	if node == nil {
		return nil,nil
	}
	for true {
		if node.Right == nil {
			return node,node.Data
		}
		node = node.Right
	}
	return nil,nil
}
func (a * AvlTree)FindMin()(*AvlNode,interface{}){
	node := a.root
	if node == nil {
		return nil,nil
	}
	for true {
		if node.Left == nil {
			return node,node.Data
		}
		node = node.Left
	}
	return nil,nil
}

type AvlNode struct {
	Left,Right *AvlNode
	Data interface{}
	Height int32
}
func (a * AvlNode)GetHeight()int32{
	if a == nil{
		return 0
	}
	return a.Height
}

//比较两个子树高度的大小
func MaxH(a, b int32) int32 {
	if a >= b {
		return a
	} else {
		return b
	}
}

//ll型 右旋
func (a *AvlNode)RightRotate()*AvlNode{
	headnode := a.Left
	a.Left = a.Left.Right
	headnode.Right = a

	a.Height = MaxH(a.Left.GetHeight(),a.Right.GetHeight()) + 1
	headnode.Height = MaxH(headnode.Left.GetHeight(),headnode.Right.GetHeight()) + 1
	return headnode
}

//rr型 左旋
func (a * AvlNode)LeftRotate()*AvlNode{
	headnode := a.Right
	a.Right = a.Right.Left
	headnode.Left = a

	a.Height = MaxH(a.Left.GetHeight(),a.Right.GetHeight()) + 1
	headnode.Height = MaxH(headnode.Left.GetHeight(),headnode.Right.GetHeight()) + 1
	return headnode
}

//lr型 先左旋左子节点，再右旋右子节点
func (a * AvlNode)LeftRightRotate()*AvlNode{
	a.Left = a.Left.LeftRotate()
	return a.RightRotate()
}

//rl型
func (a * AvlNode)RightLeftRotate()*AvlNode{
	a.Right = a.Right.RightRotate()
	return a.LeftRotate()
}

func (a * AvlNode)AdjustTree()*AvlNode{
	if a.Left.GetHeight() - a.Right.GetHeight() == 2{
		if a.Left.GetHeight()>a.Right.GetHeight(){
			return a.RightRotate()
		}else{
			return a.LeftRightRotate()
		}
	}else if a.Left.GetHeight() - a.Right.GetHeight() == -2{
		if a.Left.GetHeight()>a.Right.GetHeight(){
			return a.RightLeftRotate()
		}else{
			return a.LeftRotate()
		}
	}
	return a
}

//可以插入相同内容的数据
func (a * AvlNode)Insert(data interface{},f func(a,b interface{})int)* AvlNode{
	switch f(a.Data,data) {
	case 1:
		if a.Left == nil {
			a.Left = new(AvlNode)
			a.Data = data
			a.Height = 1
		}
		a.Left = a.Left.Insert(data,f)
	case 0:
		return a
	case -1:
		if a.Right == nil{
			a.Right = new(AvlNode)
			a.Data = data
			a.Height = 1
		}
		a.Right = a.Right.Insert(data,f)
	}
	node := a.AdjustTree()
	node.Height = MaxH(node.Left.GetHeight(),node.Right.GetHeight())+1
	return node
}

func (a * AvlNode)Delete(data interface{},f func(a,b interface{})int)* AvlNode{
	return nil
}